package mergesort;

import java.util.Arrays;

/**
 * Created by status200 on 2018/4/4.
 */
public class MergeSort {


    public static void main(String[] args) {
        int[] arr = {342,123,57,25,89,46,46,907};

        System.out.println(Arrays.toString(arr));

        mergeSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        int[] helper = new int[arr.length];

        mergeSort(arr, helper, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] helper, int start, int end) {

        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;

        mergeSort(arr, helper, start, mid);
        mergeSort(arr, helper, mid + 1, end);
        merge(arr, helper, start, mid, end);

    }

    private static void merge(int[] arr, int[] helper, int start, int mid, int end) {

        int i = start;
        int a1 = start;
        int a2 = mid + 1;

        while (i <= end && a1 <= mid && a2 <= end) {
            if (arr[a1] <= arr[a2]) {
                helper[i] = arr[a1];
                a1++;
            } else {
                helper[i] = arr[a2];
                a2++;
            }

            i++;
        }

        while(a1 <= mid) {
            helper[i++] = arr[a1++];
        }

        while(a2 <= end) {
            helper[i++] = arr[a2++];
        }

        System.arraycopy(helper, start, arr, start, end + 1 - start);

    }
}
